package com.dbh.alg.algorithm.hot100.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 2：
 *
 * 输入：s = "a"
 * 输出：[["a"]]
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 16
 * s 仅由小写英文字母组成
 */
public class Leetcode131_分隔回文 {

    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), ans);
        return ans;
    }

    /**
     * 回溯方法，用于诋毁地分隔字符串并检查回文
     * @param s 原始字符串
     * @param start 当前处理的起始位置
     * @param path 当前的分割路径(已经确认的回文子串列表)
     * @param ans 存储所有合法的分割方案
     */
    private void backtrack(String s, int start, List<String> path, List<List<String>> ans) {
        // 如果其实位置已经到达字符串末尾，说明当前路径是一个合法的分割方案
        if (start == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // 尝试从start开始的所有可能结束位置
        for (int end = start; end < s.length(); end++) {
            // 检查[start...end]是否是回文
            if (isPalindrome(s, start, end)) {
                // 如果是回文，将其加入当前路径
                path.add(s.substring(start, end + 1));
                // 递归处理剩余部分
                backtrack(s, end + 1, path, ans);
                // 回溯，移除刚才加入的子串，尝试其他可能的分割
                path.remove(path.size() - 1);
            }
        }
    }

    /**
     * 检查字符串s的子串s[left...right]是否是回文
     * @param s 原始字符串
     * @param left 子串左边界
     * @param right 子串右边界
     * @return 是否是回文
     */
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

}
